package com.sgg.datastructure.sparsearray;

public class SparseArray {
    public static void main(String[] args) {
        //初始化数组
        int[][] rawArray = new int[11][11];
        rawArray[1][2] = 1;
        rawArray[2][3] = 2;
        rawArray[4][5] = 1;
        showArray(rawArray);
        int[][] sparseArray = array2Sparse(rawArray);
        showArray(sparseArray);
        int[][] convertArray = sparse2Array(sparseArray);
        System.out.println("=============================================================");
        showArray(convertArray);
    }
    //打印数组
    public static void showArray(int[][] printArray) {
        for (int[] ints : printArray) {
            for (int val : ints) {
                System.out.printf("%d\t", val);
            }
            System.out.println();
        }
    }
    //二维数组转稀疏数组
    public static int[][] array2Sparse(int[][] rawArray) {
        int count = 0;
        for (int[] ints : rawArray) {
            for (int val : ints) {
                if (val > 0) {
                    count++;
                }
            }
        }
        System.out.println("count:" + count);
        int[][] sparseArray = new int[count + 1][3];//根据count 声明稀疏数组
        sparseArray[0][0]=rawArray.length;
        sparseArray[0][1]=rawArray[0].length;
        sparseArray[0][2]=count;
        int sparseRowIndex=0;//记录下稀疏的行
        for (int row=0;row<rawArray.length;row++) {
            for (int col=0;col<rawArray[0].length;col++) {
                if (rawArray[row][col]>0) {
                    sparseRowIndex++;
                    sparseArray[sparseRowIndex][0]=row;
                    sparseArray[sparseRowIndex][1]=col;
                    sparseArray[sparseRowIndex][2]=rawArray[row][col];
                }
            }
        }
        return sparseArray;
    }
    //稀疏数组转二维数组
    public static int[][] sparse2Array(int[][] sparseArray) {
        int[][] array=new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            //i 代表 稀疏数组的行数
            array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return array;
    }
}
